package datastructures.queues;

import java.util.Iterator;

import lib.LinearNode;

/**
 * Design note.
 * 
 * 1. Use singly linked data structure.
 * 2. use sentinel node
 * 3. use two references for nodes. One is for the first node and the other one is for the last node.
 * 2. Enqueue at the end ( complexity O(1) )
 * 3. Dequeue at the front ( complexity O(1) )
 * 4. Allow to use generic type
 *
 * @author Gatsby Lee
 */
public class LinkedQueueWithSentinelNode<T> implements QueueADT<T> {

	private int size;
	private LinearNode<T> first;
	private LinearNode<T> last;

	public LinkedQueueWithSentinelNode() {
		this.first = new LinearNode<T>(null);
		this.last = this.first;
		this.size = 0;
	}

	@Override
	public void enqueue(T element) {
		LinearNode<T> node = new LinearNode<T>(element);
		this.last.setNext(node);
		this.last = node;
		this.size++;
	}

	@Override
	public T dequeue() {
		if (this.size == 0) {
			return null;
		}

		// get the node we want to deqeue
		LinearNode<T> node = this.first.getNext();
		// Set the reference
		this.first.setNext(node.getNext());
		node.setNext(null);
		// decrement the size
		this.size--;
		// Return the element
		return node.getElement();
	}

	@Override
	public T first() {
		if (this.size != 0) {
			return this.first.getNext().getElement();
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		}
		return false;
	}

	@Override
	public int size() {
		if (this.size == 0) {
			return 0; 
		}
		return this.size;
	}

	public Iterator<T> iterator() {
		return new QueueIterator();
	}

	private class QueueIterator implements Iterator<T> {

		private LinearNode<T> currentNode = first;

		@Override
		public boolean hasNext() {
			if (this.currentNode.getNext() == null) {
				return false;
			}
			return true;
		}

		@Override
		public T next() {
			this.currentNode = this.currentNode.getNext();
			return this.currentNode.getElement();
		}

		/**
		 * This function is not supported
		 */
		@Override
		public void remove() {}
		
	}

}
